/**
 * @description 链表实现队列
 * @author 李子一
 */

interface ILinkNode {
	value: number
	next: ILinkNode | null
}

export class Queue {
	head: ILinkNode | null
	tail: ILinkNode | null
	count: number

	constructor() {
		this.head = null
		this.tail = null
		this.count = 0
	}

	add(n: number): void {
		const newNode: ILinkNode = {
			value: n,
			next: null
		}

		// 空链表的情况
		if (!this.head) {
			this.head = newNode
			/* this.tail = newNode */
		} else {
			this.tail!.next = newNode
			/* this.tail = newNode */
		}

		this.tail = newNode

		this.count++
	}

	delete(): number | null {
		if (!this.head) return null
		if (this.count <= 0) return null

		const value = this.head.value
		this.head = this.head?.next
		this.count--
		return value
	}

	get length(): number {
		return this.count
	}
}

// let q = new Queue()
// q.add(1)
// q.add(2)
// q.add(3)
// console.info(q.length)
// q.delete()
// console.info(q.length)
// q.delete()
// console.info(q.length)
// q.delete()
// console.info(q.length)
// console.log(q)

// 性能测试
const q1 = new Queue()
console.time('queue with list')
for (let i = 0; i < 100000; i++) {
	q1.add(i)
}
for (let i = 0; i < 100000; i++) {
	q1.delete()
}
console.timeEnd('queue with list')

const q2: number[] = []
console.time('queue with array')
for (let i = 0; i < 100000; i++) {
	q2.push(i)
}
for (let i = 0; i < 100000; i++) {
	q2.shift()
}
console.timeEnd('queue with array')
